#ifndef BREADTHFIRSTSEARCH_H
#define BREADTHFIRSTSEARCH_H

#include <QtCore>

#include <igraph.h>

namespace sk {

class BreadthFirstSearch {
public:
    enum Color {
        COLOR_WHITE, COLOR_GREY, COLOR_BLACK
    };

    BreadthFirstSearch(CGraph *graph, int vertex) : graph(graph), v(vertex), allocSz(graph->getVerticesCount() + 1) {
        colors = new int[allocSz];
        distances = new int[allocSz];
    }

    ~BreadthFirstSearch() {
        delete[] colors;
        delete[] distances;
    }

    virtual void process(int vertex) {
        printf("Process: %d\n", vertex);
    }

    void go() {
        memset(colors, COLOR_WHITE, sizeof(colors) * allocSz);
        memset(distances, 0, sizeof(distances) * allocSz);

        QQueue<int> q;
        q << v;
        distances[v] = 0;

        while (!q.isEmpty()) {
            int vertex = q.dequeue();

            if (!colors[vertex] == COLOR_WHITE) continue;

            process(vertex);
            colors[vertex] = COLOR_BLACK;

            foreach(int s, graph->getAdjanancies(vertex)) {
                if (colors[s] == COLOR_WHITE) {
                    q << s;
                    distances[s] = distances[vertex] + 1;
                }
            }

        }
    }

    void debug_toString() {
        printf("colors (%d)\n", allocSz);
        for (int i = 0; i < allocSz; i++)
            printf("  colors[%d] = %d\n", i, colors[i]);

        printf("distances (%d)\n", allocSz);
        for (int i = 0; i < allocSz; i++)
            printf("  distances[%d] = %d\n", i, distances[i]);
    }

private:
    CGraph *graph;
    int v;
    int allocSz;

    int* colors;
    int* distances;
};

}

#endif // BREADTHFIRSTSEARCH_H
